#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    //my ans（结果对，但是跑测试会出问题？？？）
    vector<string> ans1(vector<string>& words, int maxWidth){
        int length = words.size();
        vector<int> words_length;
        int temp;
        for(int i = 0; i != length; i++){
            temp = words[i].size();
            words_length.push_back(temp);
        }
        vector<string> out;
        int i = 0, j_begin, j_end;
        while(i < length){
            temp = maxWidth;
            int space = 0;
            j_begin = i;
            string str_temp = "";
            while(words_length[i] < temp){
                if(temp != maxWidth){
                    space++;
                    temp = temp - words_length[i] - 1;
                }else{
                    temp = temp - words_length[i];
                }
                i++;
                if(i == length){
                    break;
                }
            }
            j_end = i;
            int div_space;
            if(space == 0){
                div_space = temp;
            }else{
                div_space = temp / space;
            }

            if(i != length){  
                for(int j = j_begin; j != j_end-1; j++){
                    str_temp = str_temp + words[j] + " ";
                    if(temp % space == 0){
                        for(int k = 0; k != div_space; k++){
                            str_temp = str_temp + " ";
                        }
                    }else{
                        for(int k = 0; k != div_space+1; k++){
                            str_temp = str_temp + " ";
                        }
                        temp = temp - div_space - 1;
                        space = space - 1;
                    }
                }
                str_temp = str_temp + words[j_end-1];
            }else{
                for(int j = j_begin; j != j_end-1; j++){
                    str_temp = str_temp + words[j] + " ";
                }
                str_temp = str_temp + words[j_end-1];
                for(int k = 0; k != temp-1; k++){
                    str_temp  = str_temp + " ";
                }

            }
            out.push_back(str_temp);
        }

        return out;
    }

};

void test1(){
    Solution s;
    vector<string> words = {"This", "is", "an", "example", "of", "text", "justification."};
    int maxWidth = 16;
    vector<string> ret = s.ans1(words, maxWidth);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i] << endl;
    }
}

void test2(){
    Solution s;
    vector<string> words = {"What","must","be","acknowledgment","shall","be"};
    int maxWidth = 16;
    vector<string> ret = s.ans1(words, maxWidth);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i] << endl;
    }
}

void test3(){
    Solution s;
    vector<string> words = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
    int maxWidth = 20;
    vector<string> ret = s.ans1(words, maxWidth);
    for(int i = 0; i != ret.size(); i++){
        cout << ret[i] << endl;
    }
}

int main(void){
    test1();
    cout << "--------------------" << endl;
    test2();
    cout << "--------------------" << endl;
    test3();

    return 0;
}